package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.GraphProblem;
import cn.pugle.oj.catalog.LinkedProblem;
import cn.pugle.oj.catalog.TreeProblem;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * https://leetcode.com/problems/longest-consecutive-sequence/discuss/41057/Simple-O(n)-with-Explanation-Just-walk-each-streak
 *
 * @author tzp
 * @since 2020/10/20
 */
public class LC128_2 implements GraphProblem, TreeProblem {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int n : nums) {
            set.add(n);
        }
        int best = 0;
        for (int n : set) {
            if (!set.contains(n - 1)) {  // only check for one direction
                int m = n + 1;
                while (set.contains(m)) {
                    m++;
                }
                best = Math.max(best, m - n);
            }
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(new LC128_2().longestConsecutive(new int[]{100, 4, 200, 1, 3, 2}));
        System.out.println(new LC128_2().longestConsecutive(new int[]{100, 4, 101, 1, 102, 3, 9}));
    }
}
